Link to this headingSchorr Signature

https://conduition.io/cryptography/schnorr/

Bitcoin Implementation

Link to this headingMath

Link to this headingSingle Signature

from ecc_lib import * import hashlib from cryptopals_lib import is_prime, int_byte_length, secure_rand_between, int_to_bytes, bytes_to_int, bXXencode if __name__ == '__main__': message = b"Test Message" #Generate KeyPair privateKey, public_point = generate_KeyPair(Curve25519_Generator_Point) print(privateKey, public_point) ### Create Nonce nonce = secure_rand_between(0, Curve25519_Generator_Point.curve.prime_mod) nonce_point = nonce * Curve25519_Generator_Point print(f"Nonce: {nonce}") ### generating random biased off of know values challenge = hashlib.sha256(nonce_point.compressed() + public_point.compressed() + message).digest() #Generate Signature signature = (bytes_to_int(challenge) * privateKey) + nonce % Curve25519_Generator_Point.curve.prime_mod print(f"Signature: s:{signature}, n:{nonce_point.compressed()}") #Check Signature check1 = signature * Curve25519_Generator_Point check2 = nonce_point + (bytes_to_int(challenge) * public_point) print(f"Valid: {check1 == check2}") assert check1 == check2

Link to this headingMulti Signature

from ecc_lib import * import hashlib from cryptopals_lib import is_prime, int_byte_length, secure_rand_between, int_to_bytes, bytes_to_int, bXXencode if __name__ == '__main__': message = b"Test Message" #Generate KeyPair A private_KeyA, public_pointA = generate_KeyPair(Curve25519_Generator_Point) print(private_KeyA, public_pointA) #Generate KeyPair B private_KeyB, public_pointB = generate_KeyPair(Curve25519_Generator_Point) print(private_KeyB, public_pointB) #Generate KeyPair C private_KeyC, public_pointC = generate_KeyPair(Curve25519_Generator_Point) print(private_KeyC, public_pointC) # Generate Nonce A nonceA = secure_rand_between(0, Curve25519_Generator_Point.curve.prime_mod) nonce_pointA = nonceA * Curve25519_Generator_Point print(f"Nonce: {nonceA}") # Generate Nonce B nonceB = secure_rand_between(0, Curve25519_Generator_Point.curve.prime_mod) nonce_pointB = nonceB * Curve25519_Generator_Point print(f"Nonce: {nonceB}") # Generate Nonce C nonceC = secure_rand_between(0, Curve25519_Generator_Point.curve.prime_mod) nonce_pointC = nonceC * Curve25519_Generator_Point print(f"Nonce: {nonceC}") #Compute aggerated Nonce Point aggregated_NoncePoint = nonce_pointA + nonce_pointB + nonce_pointC #Computer Aggerated Public Key aggregated_public_point = public_pointA + public_pointB + public_pointC ### generating random biased off of know values challenge = hashlib.sha256(aggregated_NoncePoint.compressed() + aggregated_public_point.compressed() + message).digest() #Generate Signature A signatureA = (bytes_to_int(challenge) * private_KeyA) + nonceA % Curve25519_Generator_Point.curve.prime_mod signatureB = (bytes_to_int(challenge) * private_KeyB) + nonceB % Curve25519_Generator_Point.curve.prime_mod signatureC = (bytes_to_int(challenge) * private_KeyC) + nonceC % Curve25519_Generator_Point.curve.prime_mod ### Multi Signature aggregated_signature = signatureA + signatureB + signatureC print(f"Aggregated Signature: s:{aggregated_signature}, n:{aggregated_public_point.compressed()}") ### Multi Signature Check # s = (chal * privkey_a + nonce_a) + (chal * privkey_b + nonce_b) + (chal * privkey_c + nonce_c) # s = (chal * privkey_a) + (chal * privkey_b) + (chal * privkey_c) + nonce_a + nonce_b + nonce_c # s = chal * (privkey_a + privkey_b + privkey_c) + nonce_a + nonce_b + nonce_c #Check Individual Signatures check1 = signatureA * Curve25519_Generator_Point check2 = nonce_pointA + (bytes_to_int(challenge) * public_pointA) print(f"SignatureA Valid: {check1 == check2}") check1 = signatureB * Curve25519_Generator_Point check2 = nonce_pointB + (bytes_to_int(challenge) * public_pointB) print(f"SignatureB Valid: {check1 == check2}") check1 = signatureC * Curve25519_Generator_Point check2 = nonce_pointC + (bytes_to_int(challenge) * public_pointC) print(f"SignatureC Valid: {check1 == check2}") #Check Signature check1 = aggregated_signature * Curve25519_Generator_Point check2 = aggregated_NoncePoint + (bytes_to_int(challenge) * aggregated_public_point) print(f"Valid: {check1 == check2}") assert check1 == check2

Link to this headingExploits

Link to this headingMulti-Signature Rogue Key Attack

The last person to exchange keys is able to generate a Public Key rouge_public_point = public_pointC - public_pointB - public_pointA that when aggerated to the multi signature is actually the public key that the last person actually has the private key for.

This turns the multi-signature solution into a single signature solution that is controlled by the attacker.

from ecc_lib import * import hashlib from cryptopals_lib import is_prime, int_byte_length, secure_rand_between, int_to_bytes, bytes_to_int, bXXencode if __name__ == '__main__': message = b"Test Message" #Generate KeyPair A private_KeyA, public_pointA = generate_KeyPair(Curve25519_Generator_Point) #print(private_KeyA, public_pointA) #Generate KeyPair B private_KeyB, public_pointB = generate_KeyPair(Curve25519_Generator_Point) #print(private_KeyB, public_pointB) #Generate KeyPair C private_KeyC, public_pointC = generate_KeyPair(Curve25519_Generator_Point) #print(private_KeyC, public_pointC) #Generate Shared Key pair rouge_public_point = public_pointC - public_pointB - public_pointA print(rouge_public_point) # Generate Nonce A nonceA = secure_rand_between(0, Curve25519_Generator_Point.curve.prime_mod) nonce_pointA = nonceA * Curve25519_Generator_Point #print(f"Nonce: {nonceA}") # Generate Nonce B nonceB = secure_rand_between(0, Curve25519_Generator_Point.curve.prime_mod) nonce_pointB = nonceB * Curve25519_Generator_Point #print(f"Nonce: {nonceB}") # Generate Nonce C nonceC = secure_rand_between(0, Curve25519_Generator_Point.curve.prime_mod) nonce_pointC = nonceC * Curve25519_Generator_Point #print(f"Nonce: {nonceC}") #Compute aggerated Nonce Point aggregated_NoncePoint = nonce_pointA + nonce_pointB + nonce_pointC #Computer Aggerated Public Key aggregated_public_point = public_pointA + public_pointB + rouge_public_point print(f"Aggregated Point is Public point C: {aggregated_public_point == public_pointC}") assert aggregated_public_point == public_pointC ### generating random baised off of know values challenge = hashlib.sha256(aggregated_NoncePoint.compressed() + aggregated_public_point.compressed() + message).digest() #Generate Signature A signatureA = (bytes_to_int(challenge) * private_KeyA) + nonceA % Curve25519_Generator_Point.curve.prime_mod signatureB = (bytes_to_int(challenge) * private_KeyB) + nonceB % Curve25519_Generator_Point.curve.prime_mod signatureC = (bytes_to_int(challenge) * private_KeyC) + nonceC % Curve25519_Generator_Point.curve.prime_mod #print(f"Signature: s:{signatureA}, n:{nonce_pointA.compressed()}") #print(f"Signature: s:{signatureB}, n:{nonce_pointB.compressed()}") #print(f"Signature: s:{signatureC}, n:{nonce_pointC.compressed()}") ### Multi Signature aggregated_signature = signatureA + signatureB + signatureC print(f"Aggregated Signature: s:{aggregated_signature}, n:{aggregated_public_point.compressed()}") ### Multi Signature Check # s = (chal * privkey_a + nonce_a) + (chal * privkey_b + nonce_b) + (chal * privkey_c + nonce_c) # s = (chal * privkey_a) + (chal * privkey_b) + (chal * privkey_c) + nonce_a + nonce_b + nonce_c # s = chal * (privkey_a + privkey_b + privkey_c) + nonce_a + nonce_b + nonce_c #Check Indivisual Signatures check1 = signatureA * Curve25519_Generator_Point check2 = nonce_pointA + (bytes_to_int(challenge) * public_pointA) print(f"SignatureA Valid: {check1 == check2}") check1 = signatureB * Curve25519_Generator_Point check2 = nonce_pointB + (bytes_to_int(challenge) * public_pointB) print(f"SignatureB Valid: {check1 == check2}") check1 = signatureC * Curve25519_Generator_Point check2 = nonce_pointC + (bytes_to_int(challenge) * rouge_public_point) print(f"SignatureC Valid: {check1 == check2}") #Check Signature check1 = aggregated_signature * Curve25519_Generator_Point check2 = aggregated_NoncePoint + (bytes_to_int(challenge) * aggregated_public_point) print(f"Valid: {check1 == check2}") assert check1 == check2

To prevent this from happening you make each person in the signature validate that they know the secret key that they are using in the multi signature. This is done by signing some challenge and then verifying it with the attackers public key.

Link to this headingDuplicate nonces

If the nonce that generates the nonce_point is recovered by an attacker than it is possible to recover the private key. When 2 distinct messages are used, if they are the same message then no data is recovered because the signatures would be the same

d = \dfrac{s_1 - s_2}{e_1 - e_2}